Lindstr\"om theorems characterize logics in terms of model-theoreticconditions such as Compactness and the L\"owenheim-Skolem property. Mostexisting characterizations of this kind concern extensions of first-orderlogic. But on the other hand, many logics relevant to computer science arefragments or extensions of fragments of first-order logic, e.g., k-variablelogics and various modal logics. Finding Lindstr\"om theorems for theselanguages can be challenging, as most known techniques rely on coding argumentsthat seem to require the full expressive power of first-order logic. In thispaper, we provide Lindstr\"om theorems for several fragments of first-orderlogic, including the k-variable fragments for k>2, Tarski's relation algebra,graded modal logic, and the binary guarded fragment. We use two different prooftechniques. One is a modification of the original Lindstr\"om proof. The otherinvolves the modal concepts of bisimulation, tree unraveling, and finite depth.Our results also imply semantic preservation theorems.
展开▼
